class ShuDu {
    generateSudoku(n, emptyN, grid) {
        let board = Array.from({length: n}, () => Array(n).fill(0));

        this.solveSudoku(board, n, grid);

        board = this.randomEmptyCells(board, emptyN);

        return board;
    }

    randomEmptyCells(board, numEmptyCells) {
        let emptyCells = [];
        let num = board.length;
        let i = 0;

        while (emptyCells.length < numEmptyCells) {
            let row = Math.floor(Math.random() * num);
            let col = Math.floor(Math.random() * num);

            if (i < num) {
                row = i;
            }
            i++;

            if (board[row][col] === 0) {
                continue;
            }
            emptyCells.push([row, col]);
            board[row][col] = 0;
        }

        return board;
    }

    solveSudoku(board, n, grid) {
        if (!board.length) {
            return false;
        }

        let emptyCell = this.findEmptyCell(board, n);

        if (!emptyCell) {
            return true;
        }

        let row = emptyCell[0];
        let col = emptyCell[1];

        let mathArr = Array.from({length: n}, (_, i) => i + 1);
        mathArr.sort(() => Math.random() - 0.5);

        for (let num of mathArr) {
            if (this.isValidMove(board, row, col, num, n, grid)) {
                board[row][col] = num;

                if (this.solveSudoku(board, n, grid)) {
                    return true;
                }

                board[row][col] = 0;
            }
        }

        return false;
    }

    findEmptyCell(board, n) {
        for (let row = 0; row < n; row++) {
            for (let col = 0; col < n; col++) {
                if (board[row][col] === 0) {
                    return [row, col];
                }
            }
        }

        return null;
    }

    isValidMove(board, row, col, num, n, grid) {
        for (let i = 0; i < n; i++) {
            if (board[row][i] === num || board[i][col] === num) {
                return false;
            }
        }

        let startRow = row - row % grid;
        let startCol = col - col % grid;

        if (grid * grid > n) {
            return true;
        }

        for (let i = 0; i < grid; i++) {
            for (let j = 0; j < grid; j++) {
                if (board[i + startRow][j + startCol] === num) {
                    return false;
                }
            }
        }

        return true;
    }

    isValidSudoku(board, n, grid) {
        let record = [];

        for (let row = 0; row < n; row++) {
            let rowSet = {};
            for (let col = 0; col < n; col++) {
                if (board[row][col] !== 0) {
                    if (rowSet[board[row][col]]) {
                        record.push([row, col]);
                    } else {
                        rowSet[board[row][col]] = true;
                    }
                }
            }
        }

        for (let col = 0; col < n; col++) {
            let colSet = {};
            for (let row = 0; row < n; row++) {
                if (board[row][col] !== 0) {
                    if (colSet[board[row][col]]) {
                        record.push([row, col]);
                    } else {
                        colSet[board[row][col]] = true;
                    }
                }
            }
        }

        if (grid * grid > n || grid === 0) {
            return record;
        }

        for (let startRow = 0; startRow < n; startRow += grid) {
            for (let startCol = 0; startCol < n; startCol += grid) {
                let subgridSet = {};
                for (let row = startRow; row < startRow + grid; row++) {
                    for (let col = startCol; col < startCol + grid; col++) {
                        if (board[row][col] !== 0) {
                            if (subgridSet[board[row][col]]) {
                                record.push([row, col]);
                            } else {
                                subgridSet[board[row][col]] = true;
                            }
                        }
                    }
                }
            }
        }

        return record;
    }
}

let shudu = new ShuDu();
let lis = shudu.generateSudoku(9, 0, 0);
console.log(lis)
let rel = shudu.isValidSudoku(lis, 9, 3);
console.log(rel)